package core;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import core.localSerchGoodies.Pair;
import core.localSerchGoodies.TeamGroup;

public class LocalSearch {
	
	private Team[] bestSolution;
	private Team[] interpretation;
	private List<TeamGroup> group;
	private static final Random r = new Random(System.currentTimeMillis());
	public static final int NB_PERMUT=10000;
	private int nbRandomPermut=1;
	
	public LocalSearch(Team []teams){
		bestSolution=new Team[teams.length+teams.length%2];
		for(int i=0;i<teams.length;i++){
			bestSolution[i]=teams[i];
		}
		if(teams.length%2==1)
			bestSolution[teams.length]=Exemp.EXEMP;
		interpretation = new Team[bestSolution.length];
		for(int i=0;i<bestSolution.length;i++)
			interpretation[i]=bestSolution[i];
		groupSeparate();
	}

	public List<Match> search(int inNbPoints){
		init();
		setBestSolution();
		int min = getInterpretationValue();
		for(int i=0;(i<NB_PERMUT)&&(min!=0);i++){
			int bestGain=0;
			int actual = getInterpretationValue();
			if (actual<min){
				min=actual;
				setBestSolution();
			}
			List<Pair<Integer>> l =new ArrayList<Pair<Integer>>();
			for(TeamGroup g:group){
				for(Pair<Integer>p : g.getPermutationList()){
					permut(p.getFirstElement(),p.getSecondElement());
					int gain = actual - getInterpretationValue();						
					permut(p.getFirstElement(),p.getSecondElement());
					if(gain>bestGain){
						l.clear();
						bestGain=gain;
					}
					if(gain==bestGain){
						l.add(p);
					}
				}
			}
			if(bestGain>0){
				Pair<Integer>p=l.get(r.nextInt(l.size()));
				permut(p.getFirstElement(), p.getSecondElement());
			}
			else randomPermut();
		}		
		return createMatchList(inNbPoints);
	}
	
	private static int luby(int i)
	{
	    int power;
	    int k;
	    assert(i>0);
	    k = 1;
	    power = 2;
	    while (power < (i+1))
	      {
	    	k += 1;
	    	power *= 2;
	      }
	    if (power == (i+1)) return (power/2);
	    return (luby(i - (power/2) + 1));
	}

	
	private void randomPermut() {
		int nb=luby(nbRandomPermut++);
		for(int i=0;i<nb;i++){
			TeamGroup g = group.get(r.nextInt(group.size()));
			List<Pair<Integer>> l =g.getPermutationList() ;
			if(l.size()>0){
				Pair<Integer> p = l.get(r.nextInt(l.size()));
				permut(p.getFirstElement(),p.getSecondElement());
			}
		}
	}

	private List<Match> createMatchList(int inNbPoints) {
		List<Match> res=new ArrayList<Match>();
		for(int i=0;i<bestSolution.length;){
			res.add(new Match(bestSolution[i],bestSolution[i+1],inNbPoints));
			i+=2;
		}
		return res;
	}

	private void init() {
		List<Team> l=new ArrayList<Team>();
		for(TeamGroup g:group){
			for(int i=g.getBeginIndex();i<=g.getEndIndex();i++)
				l.add(interpretation[i]);
			for(int i=g.getBeginIndex();i<=g.getEndIndex();i++)
				interpretation[i]=l.remove(r.nextInt(l.size()));				
		}
	}

	private void groupSeparate() {
		group=new ArrayList<TeamGroup>();
		int begin=0;
		for(int i=1;i<interpretation.length;i++){
			if(interpretation[i].getWinPoints()!=interpretation[begin].getWinPoints()){
				group.add(new TeamGroup(begin,i-1));
				begin = i;
			}
		}
		group.add(new TeamGroup(begin,interpretation.length-1));
	}

	private int getInterpretationValue(){
		int res=0;
		for(int i=0;i<interpretation.length;){
			res+=interpretation[i+1].nbMatchVs(interpretation[i].getId());
			i+=2;
		}
		return res;
	}
	
	private void setBestSolution(){
		for(int i=0;i<bestSolution.length;i++){
			bestSolution[i]=interpretation[i];
		}
	}
	
	private void permut(int i,int j){
		Team aux =interpretation[i];
		interpretation[i]=interpretation[j];
		interpretation[j]=aux;
	}
	
}
